package com.algorithms.techniques;

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Queue;

import com.algorithms.absdatatypes.Graph;
import com.algorithms.absdatatypes.GraphNode;
import com.algorithms.absdatatypes.AbstractGraph.GraphEntry;
import com.algorithms.absdatatypes.Apply.GRAPH_DIRECTION;
import com.algorithms.absdatatypes.Apply.GRAPH_EDGE_DIRECTION;
import com.algorithms.datatypes.DefaultGraph;

public class GraphSearch {
	public static int GraphNodeInfinity = 999999999;

	public static <K extends Comparable, T, NM extends Number> LinkedHashMap<GraphNode<K, T>,Integer> breadthFirstSearch(
			Graph<K, T, NM> inputGraph,GraphNode<K, T> startNode) 
	{
		Graph<K,T,Integer> returnGraph = new DefaultGraph<K,T,Integer>(GRAPH_DIRECTION.DIRECTED);
		LinkedHashMap<GraphNode<K, T>,Integer> returnDistanceMap = new LinkedHashMap<GraphNode<K, T>,Integer>();
		
		/*
		 * Set all the edges in the new graph having size of infinity
		 */
		for (GraphNode<K, T> vertex1 : inputGraph.getAdjacencyList().keySet()) 
		{
			if (inputGraph.getAdjacencyList().get(vertex1) != null)
			{
				for (GraphEntry<GraphNode<K, T>, NM> vertex1ConnectedTo : inputGraph.getAdjacencyList()
						.get(vertex1)) 
				{
					returnGraph.addVertex(vertex1);
					returnGraph.addVertex(vertex1ConnectedTo.getKey());
					returnGraph.addEdge(vertex1, vertex1ConnectedTo.getKey(), GraphSearch.GraphNodeInfinity,GRAPH_EDGE_DIRECTION.LEFTTORIGHT);
				}
			}
		}
		/*
		 * output the path
		 */
		Queue<GraphNode<K, T>> queue = new LinkedList<GraphNode<K, T>>();
		queue.offer(startNode);
		returnDistanceMap.put(startNode,0);
		int distance=0;
		while(!queue.isEmpty())
		{
			GraphNode<K, T> graphNode= queue.poll();
			distance=returnDistanceMap.get(graphNode) +1;
			if(inputGraph.getAdjacencyList().get(graphNode)!=null)
			{
				for (GraphEntry<GraphNode<K, T>, NM> vertex1 : inputGraph.getAdjacencyList().get(graphNode)) 
				{
					
					if(returnDistanceMap.get(vertex1.getKey())!=null)
					{
						//Do nothing
					}
					else
					{
						queue.add(vertex1.getKey());
						returnDistanceMap.put(vertex1.getKey(),distance);
					}
				}
			}
			
		}
		return returnDistanceMap;
	}

}
